/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
import binaryTree.BinaryTree;
import java.io.File;
import java.math.BigInteger;
import java.util.ArrayList;
import org.springframework.util.StopWatch;

/**
 *
 * @author esohsin
 */
public class EulerProblems {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        //BigInteger myNumber = new BigInteger("600851475143") ;
        
        //euler 3
        //prime(myNumber);
        
        //euler 4
        //largest_palindrome_product(4);
        
        //euler5
        //int n = 20;
        //System.out.println("Smallest multiple untill " + n + " : " + findSmallestMultiple(n));
        
        //euler6
        //euler6();
        
        //euler 7
        //int n = 10001;
        //System.out.println("The " + n + "th Prime number = " + findPrime(new BigInteger(String.valueOf(n))));
        
        //euler 8
        //euler8();
        
        //euler9
        //executeAndShowRunTime(new Runnable(){public void run() {euler9();} });
        
        //euler10
        //executeAndShowRunTime(new Runnable(){public void run() {euler10();} });
        
        //euler11
        //executeAndShowRunTime(new Runnable(){public void run() {euler11();} });
        
        //euler12
        //executeAndShowRunTime(new Runnable(){public void run() {euler12();} });
        //prime(new BigInteger("39"));
        
        //euler13
        //executeAndShowRunTime(new Runnable(){public void run() {euler13();} });
        
        //euler14
        //executeAndShowRunTime(new Runnable(){public void run() {euler14();} });
        
        //euler16
        //executeAndShowRunTime(new Runnable(){public void run() {euler16();} });
        
        //euler17
        //executeAndShowRunTime(new Runnable(){public void run() {euler17();} });
        
        //euler18
        executeAndShowRunTime(new Runnable(){public void run() {euler18();} });
    }
    
    private static void executeAndShowRunTime(Runnable method)
    {
        StopWatch sw = new StopWatch();
        sw.start();
        method.run();
        sw.stop();
        System.out.println("This solution takes " + sw.getTotalTimeMillis() + " ms.");
    }
    
    //largest prime factor euler 3
    private static void prime(BigInteger n)
    {
        while(n.divideAndRemainder(new BigInteger("2"))[1].equals(new BigInteger("0")))
        {
            n = n.divide(new BigInteger("2"));
        }
        
        BigInteger divider = new BigInteger("3");
        BigInteger result = null;
        while(divider.multiply(divider).compareTo(n) <= 0)
        {
            if(n.divideAndRemainder(divider)[1].equals(new BigInteger("0")))
            {
                n = n.divide(divider);
                result = n;
            }
            else
            {
                divider = divider.add(new BigInteger("2"));
            }
        }
        System.out.println(result.toString(10));
    }
    
    //largest palindrome product generic //euler 4
    private static void largest_palindrome_product(int n)
    {
        //firstly solving it for n=3 and then will go for generic solution
        //n = 3 for euler problem 4
        //largest result of multiplication of two 3-digit numbers:
        //999*999 = 998001 so, the largest palindrome of 6 digit is 997799 within our constraint
        //so we will make paindrome from this number using '997'
        //then using 996, we will get 996699 and so on...
        //if we find a 6digit palidrome which is product of 3-digit number we will not further find
        //a 5-digit palindrome
        //else we will go for 5digit palindrome.
        //we will make 5digit palindrome by same formula with a twist
        //eg. using '998' we will make 99899 and 
        //the last '99' is just taken reversly after the last digit i.e 8
        
        int startingPart = (int) (Math.pow(10, n) - 2);
        int ourPalindrome;
        boolean hopeDoubleDigitFound = true;//if we have dope to 6digit palindrome finding
        boolean found = false;//the ultimate quest :P
        do
        {
            startingPart--;
            if(hopeDoubleDigitFound)
                ourPalindrome = buildPalindrome(startingPart, 2*n);
            else
                ourPalindrome = buildPalindrome(startingPart, 2*n-1);
            for(int i = (int) (Math.pow(10, n) - 1); i >= (int) Math.pow(10, n - 1); i--)
            {
                //check if the other factor is already greater than 999 then no need to check further
                //and also if the square root of ourPalindrome has come
                //if it has come that means it's prime number as it doesn't contain any factor from 999
                //to that number so it's must be a prime
                if(ourPalindrome/i > (int) (Math.pow(10, n) - 1) || i * i < ourPalindrome)
                {
                    break;
                }
                
                if(ourPalindrome % i == 0)
                {
                    found = true;
                    System.out.print("The largest Palindromic Number of digit "+ n +" is:" + ourPalindrome);
                    System.out.println(", got by " + i + "*" + (ourPalindrome / i));
                    break;
                }
            }
            if(ourPalindrome == 100001)
            {
                hopeDoubleDigitFound = false;
            }
        }
        while(!found);
    }
    
    private static int buildPalindrome(int fusingNumber, int digit)
    {
        String startingPart = String.valueOf(fusingNumber);
        String reverse = null;
        if(digit%2 == 0)
        {
            reverse = new StringBuffer(startingPart).reverse().toString();
        }
        else
        {
            reverse = new StringBuffer(startingPart).reverse().toString().substring(1);
        }
        return Integer.parseInt(startingPart + reverse);
    }
    
    /**
     * Find nth Prime number
     * @param n give n as a BigInteger eg. - BigInteger("123234")
     * @return returns a BigInteger which is nth prime number
     */
    private static BigInteger findPrime(BigInteger n)
    {
        BigInteger myProbablePrime = new BigInteger("2");
        BigInteger iterator = new BigInteger("1");
        
        while(true)
        {
            BigInteger count = new BigInteger("2");
            boolean remainderFound = false;
            for(; count.multiply(count).compareTo(myProbablePrime)<= 0; count = count.add(new BigInteger("1")))
            {
                if(myProbablePrime.divideAndRemainder(count)[1].equals(new BigInteger("0")))
                {
                    remainderFound = true;
                    break;
                }
            }
            if(!remainderFound)
            {
                iterator = iterator.add(new BigInteger("1"));
                if(iterator.compareTo(n) > 0)
                {
                    break;
                }
            }
            myProbablePrime = myProbablePrime.add(new BigInteger("1"));
        }
        return myProbablePrime;
    }
    
    private static void euler8()
    {
        String input = "73167176531330624919225119674426574742355349194934" +
                        "96983520312774506326239578318016984801869478851843" +
                        "85861560789112949495459501737958331952853208805511" +
                        "12540698747158523863050715693290963295227443043557" +
                        "66896648950445244523161731856403098711121722383113" +
                        "62229893423380308135336276614282806444486645238749" +
                        "30358907296290491560440772390713810515859307960866" +
                        "70172427121883998797908792274921901699720888093776" +
                        "65727333001053367881220235421809751254540594752243" +
                        "52584907711670556013604839586446706324415722155397" +
                        "53697817977846174064955149290862569321978468622482" +
                        "83972241375657056057490261407972968652414535100474" +
                        "82166370484403199890008895243450658541227588666881" +
                        "16427171479924442928230863465674813919123162824586" +
                        "17866458359124566529476545682848912883142607690042" +
                        "24219022671055626321111109370544217506941658960408" +
                        "07198403850962455444362981230987879927244284909188" +
                        "84580156166097919133875499200524063689912560717606" +
                        "05886116467109405077541002256983155200055935729725" +
                        "71636269561882670428252483600823257530420752963450";
        int myMultipliedResult = 0;
        for(int i = 0; i < 996; )
        {
            String sub5 = input.substring(i, i + 5);
            System.out.println(sub5 + "**");
            int incr = checkZero(sub5);
            if(incr != -1)
            {
                
                i+= (incr+1);
                System.out.print("\nSkipped to " + i + "\n");
            }
            else
            {
                int result = multiplyStringData(sub5);
                if(myMultipliedResult < result)
                {
                    myMultipliedResult = result;
                    //System.out.print(myMultipliedResult + "**");
                }
                i++;
            }
        }
        System.out.print("\nLargest Multiplication result:" + myMultipliedResult);
    }
    
    /**
     * Helper method of euler8
     * @param input
     * @return 
     */
    private static int multiplyStringData(String input)
    {
        int result = 1;
        for(int i = 0; i < input.length(); i++)
        {
            result = result * Character.getNumericValue(input.charAt(i));
        }
        return result;
    }
    
    /**
     * Helper method of multiplyStrindData
     * @param input
     * @return 
     */
    private static int checkZero(String input)
    {
        for(int i = input.length() - 1; i > -1; i--)
        {
            if(input.charAt(i) == '0')
            {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * smallest multiple till limit
     * @param limit the limit till which we want to find smallest multiple
     * @return 
     */
    private static long findSmallestMultiple(int limit)
    {
        long result = 1;
        if(limit <= 1)
        {
            System.out.println("Not True for less than 1");
        }
        else
        {
            for(int i = 2; i <= limit; i++)
            {
                result = lcm(result, i);
            }
        }
        return result;
    }
    
    private static long lcm(long a, long b)
    {
        long result = 1;
        long max = a, min = b;
        if(max < min)
        {
            min = a;
            max = b;
        }
        for(int i = 1; i <= min; i++)
        {
            if((max * i) % min == 0)
            {
                result = i * max;
                break;
            }
        }
        return result;
    }
    
    private static boolean isPrime(BigInteger n)
    {
        for(BigInteger i = new BigInteger("2"); (i.multiply(i)).compareTo(n) <= 0; i = i.add(new BigInteger("1")))
        {
            if((n.divideAndRemainder(i)[1]).compareTo(new BigInteger("0")) == 0)
            {
                return false;
            }
        }
        return true;
    }
    
    /**
     * Euler problem number 6
     */
    private static void euler6()
    {
        //Ans = 2(ab+ac+ad+...)
        
        //StringBuilder myInput = new StringBuilder();
        //for(int i = 0; i < 100; i++)
            //myInput.append("D");
        int result = 0;
        //ArrayList<String> combinationsOf2 = new ArrayList<>();
        
        //combination(myInput.toString(), 2, combinationsOf2);
        
        for(int i = 0; i < 100; i++)
        {
            for(int j = i+1; j < 100; j++)
            {
                System.out.println((i+1) + "-" + (j+1));
                result+= (i+1) * (j+1);
            }
            //String[] each = combinationsOf2.get(i).split("-");
            //System.out.println(each[0] + "-" + each[1]);
            //result+= Integer.parseInt(each[0]) * Integer.parseInt(each[1]);
        }
        
        result *= 2;
        System.out.println("Result is " + result);
    }
    
    private static String[] combination(String input, int noLetter, ArrayList<String> auxResult)
    {
        ArrayList<String> result = new ArrayList<>();
        int total = (int) Math.pow(2, input.length());
        int resultI = 0;
        for(int i = 0; i < total; i++)
        {
            String inputEquivBin = makeInputEquivalent(Integer.toBinaryString(i), input.length());
            StringBuilder eachString = new StringBuilder();
            StringBuilder eachAuxString = new StringBuilder();
            for(int j = 0; j < inputEquivBin.length(); j++)
            {
                if(inputEquivBin.charAt(j) == '1')
                {
                    eachAuxString.append((j+1) + "-");
                    eachString.append(input.charAt(j));
                }
                if(eachString.length() > noLetter)
                    break;
            }
            if(noLetter == eachString.length())
            {
                //System.out.println(eachString.toString() + "--" + inputEquivBin);
                String[] each = eachAuxString.toString().split("-");
                System.out.println(each[0] + "-" + each[1]);
                resultI+= Integer.parseInt(each[0]) * Integer.parseInt(each[1]);
                result.add(eachString.toString());
                auxResult.add(eachAuxString.toString());
            }
        }
        
        //Java cannot blindly downcast Object[] to String[]
        //if it can then it would violate the type safety.
        //so we need to provide the type which it will follow to make the conversion(downcasting)
        System.out.append("Result is " + 2*resultI);
        return result.toArray(new String[1]);
    }
    
    private static String makeInputEquivalent(String myString, int inputLength)
    {
        StringBuilder result = new StringBuilder();
        result.append(myString);
        if(myString.length() == inputLength)
        {
            return result.toString();
        }
        else if(myString.length() < inputLength)
        {
            for(int i = 0; i < inputLength - myString.length(); i++)
            {
                result.insert(0, '0');
            }
            return result.toString();
        }
        else
        {
            result.substring(myString.length() - inputLength);
        }
        return null;
        
    }
    
    /**
     * Euler Problem number 9
     */
    private static void euler9()
    {
        int a = 1, a2,
            b = 1, b2,
            c = 1, c2;
        while(true)
        {
            a2 = a * a;
            b = a + 1;
            c = b + 1;
            while(c < 1000)//random take 1000
            {
                c2 = a2 + b * b;
                while(c * c < c2)
                {
                    c = c + 1;
                }
                if(c * c == c2 && c < 1000)
                {
                    //System.out.println("A, B, C are " + a + "," + b + "," + c + "-" + (a*b*c));
                    if(a + b + c == 1000)
                        break;
                }
                b++;
            }
            if(a + b + c == 1000)
                        break;
            a++;
        }
        System.out.println("Ultimate A, B, C are " + a + "," + b + "," + c + "-" + (a*b*c));
    }
    
    private static int[] pythagoreanTripletN(int limit)
    {
        int triplet[] = new int[3];
        return triplet;
    }
    
    private static void euler10()
    {
        BigInteger sum = new BigInteger("10"),
                   zero = new BigInteger("0"),
                   two = new BigInteger("2"),
                   three = new BigInteger("3"),
                   five = new BigInteger("5");
        String limit = "2000000";
        for(BigInteger i = new BigInteger("6"); i.compareTo(new BigInteger(limit)) <= 0; i = i.add(new BigInteger("1")))
        {
            if( (i.divideAndRemainder(two)[1]).compareTo(zero) == 0
                || (i.divideAndRemainder(three)[1]).compareTo(zero) == 0
                    || (i.divideAndRemainder(five))[1].compareTo(zero) == 0)
            {
                continue;
            }
            else
            {
                if(isPrime(i))
                {
                    sum = sum.add(i);
                }
            }
        }
        System.out.println("Summation of prime up to " + limit + " is:" + sum.toString(10));
    }
    
    //brute-force solution
    //checking right, left, up, bottom and left-bottom and right-bottom
    private static void euler11()
    {
        In myFile = new In("euler11.txt");
        int size = 20;
        if(myFile.exists())
        {
            long [][]grid = new long[size][size];
            for(int i = 0; i < size; i++)
                for(int j = 0; j < size; j++)
                    grid[i][j] = myFile.readLong();
            
            long max = 0;
            for(int i = 0; i < size; i++)
            {
                for(int j = 0; j < size; j++)
                {
                    long temp;
                    if(j + 4 < size)//Right Side
                    {
                        temp = multiply(new long[]{grid[i][j], grid[i][j+1], grid[i][j+2], grid[i][j+3]});
                        if(max < temp)
                            max = temp;
                        if(i + 4 < size)//right-bottom diagonal
                        {
                            temp = multiply(new long[]{grid[i][j], grid[i+1][j+1], grid[i+2][j+2],
                                            grid[i+3][j+3]});
                            if(max < temp)
                                max = temp;
                        }
                    }
                    if(j - 3 >= 0)//left side
                    {
                        temp = multiply(new long[]{grid[i][j], grid[i][j-1], grid[i][j-2], grid[i][j-3]});
                        if(max < temp)
                            max = temp;
                        if(i + 4 < size)//left-bottom diagonal
                        {
                            temp = multiply(new long[]{grid[i][j], grid[i+1][j-1], grid[i+2][j-2],
                                            grid[i+3][j-3]});
                            if(max < temp)
                                max = temp;
                        }
                    }
                    if(i + 4 < size)//bottom side
                    {
                        temp = multiply(new long[]{grid[i][j], grid[i+1][j], grid[i+2][j], grid[i+3][j]});
                        if(max < temp)
                            max = temp;
                    }
                    if(i - 3 >= 0)//up side
                    {
                        temp = multiply(new long[]{grid[i][j], grid[i-1][j], grid[i-2][j], grid[i-3][j]});
                        if(max < temp)
                            max = temp;
                    }
                                        
                }
            }
            
            System.out.println("Maximum: " + max);
            
        }
        else
        {
            System.out.println("File doesn't exist.");
        }
    }
    
    private static long multiply(long[] input)
    {
        long result = 1;
        for(int i = 0; i < input.length; i++)
        {
            result *= input[i];
            if(input[i] == 0) break;
        }
        return result;
    }
    
    private static void euler12()
    {
        long n = 1;
        long i = 1;
        //numberOfDivisors(97);
        while(numberOfDivisors(n) < 500)
        {
            //int m = numberOfDivisors(n);
            //System.out.println("Result:" + " for " + n + " upto " + i);
            //if(m > 500)
                //break;
            i++;
            n += i;
        }
        System.out.println("Result:" + numberOfDivisors(n) + " for " + n);
    }
    private static int numberOfDivisors(long n)
    {
        int result = 1;
        
        /*if(isPrime(new BigInteger(String.valueOf(n))))
        {
            return 2;
        }*/
        
        long number = n, lastDivisor = -1;
        long ithPrimeDivisorSExponent;
        for(long i = 2; i * i <= number; i++)
        {
            if(n % i == 0)
            {
                //System.out.print("\n");
                ithPrimeDivisorSExponent = 0;
                do
                {
                    //System.out.print(i + " ");
                    ithPrimeDivisorSExponent += 1;
                    n /= i;
                }
                while(n % i == 0);
                lastDivisor = i;
                result *= (ithPrimeDivisorSExponent + 1);
            }
        }
        //System.out.print("\n");
        if(lastDivisor != n && n != 1)
        {
            //System.out.print(n/* + " " + lastDivisor*/);
            result *= (1 + 1);
        }
        //System.out.print("\n");
        //for(int i = 0; i < primeDivisors.length; i++)
        //{
            //result *= (primeDivisors[i] + 1);
        //}
        return result;
    }
    
    private static void euler13()
    {
        In myFile = new In("euler13.txt");
        BigInteger myString[] = new BigInteger[100];
        int i = 0;
        while(myFile.hasNextLine())
        {
            myString[i] = new BigInteger(myFile.readString());
            i++;
        }
        
        System.out.println(sumAll(myString).toString().substring(0, 10));
    }
    
    private static BigInteger sumAll(BigInteger[] input)
    {
        BigInteger result = new BigInteger("0");
        for(int i = 0; i < input.length; i++)
        {
            System.out.println("Working " + i + input[i].toString());
            result = result.add(input[i]);
        }
        return result;
    }
    
    private static void euler14()
    {
        BigInteger myNumber = new BigInteger("1000000");
        BigInteger result = new BigInteger("0");
        BigInteger theNumber = null;
        while(true)
        {
            BigInteger current = numberinCollatzSeq(myNumber);
            if(result.compareTo(current) < 0)
            {
                theNumber = myNumber;
                result = current;
            }
            //System.out.println("--" + result.toString()+"," + myNumber.toString()+"--"+theNumber.toString());
            myNumber = myNumber.subtract(new BigInteger("1"));
            if(myNumber.intValue() == 1)
                break;
        }
        System.out.println(theNumber.toString());
        //we can improve this by caching but that would not be too fancy thing to do.
    }
    
    private static BigInteger numberinCollatzSeq(BigInteger n)
    {
        BigInteger total = new BigInteger("0");
        while(true)
        {
            //System.out.print(n.toString());
            total = total.add(new BigInteger("1"));
            if(n.intValue() == 1)
                break;
            //System.out.print("->");
            if(n.testBit(0))
            {
                n = (n.multiply(new BigInteger("3"))).add(new BigInteger("1"));
                
            }
            else
            {
                n = n.shiftRight(1);
                //n = n.divide(new BigInteger("2"));
            }
        }
        //System.out.print(total.toString());
        return total;
    }
    
    private static void euler16()
    {
        BigInteger myNumber = new BigInteger("2").pow(1000);
        String myNumberString = myNumber.toString();
        int result = 0,
            i = 0,
            length = myNumberString.length();
        
        while(i < length)
        {
            result += Character.getNumericValue(myNumberString.charAt(i++));
        }
        System.out.println("The sum of digits in 2^1000: " + result);
    }
    
    private static void euler17()
    {
        int result = 0;
        for(int i = 1; i <= 1000; i++)
            result += lengthOfNumberInAplha(i).length();
        System.out.println("Length of upto 1000 is " + result);
    }
    
    /**
     * upto 1000
     * @param num
     * @return 
     */
    private static String lengthOfNumberInAplha(int num)
    {
        String result = new String();
        
        if(num / 100 > 0 && num / 100 < 10)
        {
            result += getLengthFirst(num / 100);//Hundreadth
            result += "Hundred";//hundread
            if(num % 100 > 0)
            {
                result += "And"; //and
            }
        }
        else if(num == 1000)
            return "OneThousand";
        
        num = num % 100;
        
        if(num >= 1 && num <= 9)
        {
            result += getLengthFirst(num % 10);//First Digit from left
        }
        else if(num >= 10 && num <= 19)
        {
            result += getLengthSecondWithOne(num % 10);//Eleven, Twelve
        }
        else
        {
            result += getLengthSecond(num / 10);//second digit from left
            result += getLengthFirst(num % 10);//First Digit from left
        }
        //System.out.println(result);
        return result;
    }
    
    private static String getLengthFirst(int number)
    {
        switch(number)
        {
            case 1:
                return "One";
            case 2:
                return "Two";
            case 3:
                return "Three";
            case 4:
                return "Four";
            case 5:
                return "Five";
            case 6:
                return "Six";
            case 7:
                return "Seven";
            case 8:
                return "Eight";
            case 9:
                return "Nine";
        }
        return "";
    }
    
    private static String getLengthSecondWithOne(int number)
    {
        switch(number)
        {
            case 0:
                return "Ten";
            case 1:
                return "Eleven";
            case 2:
                return "Twelve";
            case 3:
                return "Thirteen";
            case 4:
                return "Fourteen";
            case 5:
                return "Fifteen";
            case 6:
                return "Sixteen";
            case 7:
                return "Seventeen";
            case 8:
                return "Eighteen";
            case 9:
                return "Nineteen";
        }
        return "";
    }
    
    private static String getLengthSecond(int number)
    {
        switch(number)
        {
            case 1:
                return "";
            case 2:
                return "Twenty";
            case 3:
                return "Thirty";
            case 4:
                return "Forty";
            case 5:
                return "Fifty";
            case 6:
                return "Sixty";
            case 7:
                return "Seventy";
            case 8:
                return "Eighty";
            case 9:
                return "Ninety";
        }
        return "";
    }
    
    private static void euler18()
    {
        In myFile = new In("euler18.txt");
        int[] myList = new int[10000];
        int listCount = 0;
        int numberOfLines = 0;
        while(myFile.hasNextLine())
        {
            numberOfLines++;
            String[] lineIntegers = myFile.readLine().split(" ");
            for(int i = 0; i < lineIntegers.length; i++)
            {
                myList[listCount++] = Integer.parseInt(lineIntegers[i]);
            }
        }
        //listCount--;
        //printList(myList, numberOfLines);
        int x = numberOfLines - 1, y = numberOfLines - 1;
        for(int i = (listCount - numberOfLines - 1); i >= 0; i--)
        {
            myList[i] += Math.max(myList[i + x], myList[i + x + 1]);
            y--;
            if(y == 0)
            {
                y = --x;
            }
            //printList(myList, numberOfLines);
        }
        
        System.out.println("Result = " + myList[0]);
    }
    
    private static void printList(int []list, int total)
    {
        int x = 0;
        for(int i = 0; i < total; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                System.out.print(list[x++] + " ");
            }
            System.out.println();
        }
    }
}